1. Field of the Present Invention
The present invention relates generally to the field of computer systems, and more particularly, to the field of random number generators for use by computer systems.
2. Background
As is well known, many computer and other electronic systems rely on processes that make use of random numbers. Examples of applications operating on such systems or making use of such processes include lotteries, gambling machines, video games, image processing and reconstruction, music and graphics composition, scientific and financial modeling simulation, program and algorithm testing, equation-solving, and computer security. In particular, computer security applications such as cryptography, digital signatures, and protected communication protocols, make use of random numbers as a fundamental building block for strengthening and securing the confidentiality of electronic communications.
As is also well known, cryptography is the art and science of converting data or other information from its normal, easily comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge. In contemporary usage, cryptography is often used to provide security for the communications that occur between separate computer devices, sometimes referred to herein as an entity, and involves authentication, confidentiality, and integrity.
Authentication involves ensuring each entity communicating with one another is who the other entity or entities think it is. In an exemplary authentication protocol, a first entity of a type referred to as a client requests access, over a network, to password-protected information that is stored on a second entity of a type referred to as a server. The server responds with a random challenge, which is typically a random number that is often combined with other information. The client encrypts the random challenge using a password as a key and returns the encrypted challenge to the server. The server encrypts the same random challenge with the client's password, which the server obtains from its own password database. The server compares the two results, and if the results match, then the server has thereby authenticated the client without the client ever sending its password over the network. The generation and use of random numbers are thus critical in ensuring that no unauthorized entity observing an encrypted random challenge can impersonate the client by similarly responding to new random challenges.
Confidentiality, on the other hand, involves ensuring that no unauthorized entity listening to a communication is able to extract meaningful information from the data being communicated back and forth. Confidentiality is typically provided through data encryption which is the process of combining the original message with a cryptographic key in a defined manner to encrypt the message. In an ideal cryptosystem, only an entity with a particular decryption key can decrypt the encrypted message. By ensuring that this decryption key cannot be predicted or replicated and that only the intended recipient of the message has the required decryption key, the message can be protected from observation by an unauthorized entity.
Cryptographic keys can be symmetric or asymmetric. A symmetric key may be used for both encrypting data and decrypting the same data. On the other hand, asymmetric keys are produced in pairs, with each pair including a public key for encrypting data and a private key for decrypting data. The strength of a cryptosystem lies in the strength of the key which is a function of not only the number of bits in the key but also the randomness of the number used to generate the key. The generation and use of random numbers are thus critical in ensuring the confidentiality of a message.
Finally, integrity involves ensuring that no undetected changes are made to a particular communication. This may be accomplished using digital signatures. A digital signature is a fixed-length binary string unique to a given message and signed with a private key. The unique string is typically known as a message digest or cryptographic hash. Because the unique string is signed with the originating entity's private key, any entity with the originating entity's public key can decrypt the message and identify the owner of the private key and thereby identify the entity that originated the message. By generating another hash of the message using the same hashing algorithm as the originating entity and comparing the new hash with the signed hash, the recipient can verify that the message did not change after leaving the originator. The generation and use of random numbers is thus critical in ensuring that a signature generated using random numbers is of sufficient strength to avoid forgery of the signature.
In computer and other electronic systems, random numbers are a sequence of independent numbers with a specified distribution and a specified probability of falling in any given range of values. An ideal random number generator provides a stream of uniformly distributed, non-deterministic, independent bits over an infinite data set. A wide variety of random number generators have been created in an attempt to reach this ideal. Unfortunately, to a greater or lesser degree, known random number generators fall short of this ideal, and instead provide only what more properly is characterized as pseudorandom numbers.
For example, computer systems often use modular software-based random number generators. These solutions are typically created independently and then added to a computer system with relative ease. Unfortunately, software random number generators typically require a seed which is used as an operand in a mathematical algorithm to create a random number. The sequence of numbers generated by such software random number generators will eventually repeat, however, thus making it easier to predict a particular random number generator, thereby diminishing its usefulness.
Incorporating randomness into the seed and using sufficiently long mathematical computations help to increase the randomness of the numbers generated thereby. Typically, the seed is generated from bits of data collected from data sources within the computer system, including such the system clock, processes executing in the computer system, status registers, keystrokes, key press timing, and mouse movements, and the like. System interrupts and event handling, however, may reduce the effective randomness of at least some of these seed sources within different computer systems. Thus, a need exists for a random data generator that is more likely to be able to generate non-repeating random or pseudorandom numbers than previously possible.
Another drawback of existing random number generators is their susceptibility to decryption, decoding, deciphering or the like through a combination of traditional cryptography techniques and traffic analysis. In other words, by examining a sufficient number of random numbers generated by the generator, it may be possible to derive information about the generation process, thereby making it easier to predict future random numbers. As computer analysis techniques and processing capabilities become ever-greater, this poses a serious threat to the security of known random number generators. A more secure random data generator is thus needed in order to prevent such activities.